#pragma once

////节点
	//template<typename T>
	//struct List_node
	//{
	//	T _data;
	//	List_node<T>* _prev;
	//	List_node<T>* _next;
	//};

	//template<typename T>
	//class list
	//{
	//	typedef struct List_node<T> node;

	//private:
	//	node* _head;
	//	size_t _size;
	//};

#include <iostream>
#include <assert.h>
#include <vector>
#include <string>
using namespace std;


namespace xsc 
{
	//节点
	template<typename T>
	struct List_node
	{
		T _data;
		List_node<T>* _prev;
		List_node<T>* _next;

		List_node(const T& val = T())
			:_data(val)
			,_prev(nullptr)
			,_next(nullptr)
		{}
	};

	//iterator
	template <typename T, typename Ref ,typename Ptr>
	struct List_iterator
	{
		typedef struct List_node<T> node;
		typedef struct List_iterator<T,Ref,Ptr> Self;
		node* _node;

		List_iterator(node* node) :
			_node(node)
		{}


		Ref operator*()
		{
			return _node->_data;
		}

		Self& operator++()
		{
			_node = _node->_next;

			return *this;
		}

		Self& operator--()
		{
			_node = _node->_prev;

			return *this;
		}

		Self& operator++(int)
		{
			Self tmp(*this);

			_node = _node->_next;

			return tmp;
		}

		Self& operator--(int)
		{
			Self tmp(*this);
			_node = _node->_prev;

			return tmp;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

		bool operator==(const Self& s)
		{
			return _node == s._node;
		}
	};

	////const迭代器
	//template <typename T>
	//struct const_List_iterator
	//{
	//	typedef struct List_node<T> node;
	//	typedef struct const_List_iterator<T> Self;
	//	node* _node;

	//	const_List_iterator(node* node) :
	//		_node(node)
	//	{}


	//	const T& operator*()
	//	{
	//		return _node->_data;
	//	}

	//	const Self& operator++()
	//	{
	//		_node = _node->_next;

	//		return *this;
	//	}

	//	bool operator!=(const Self& s)
	//	{
	//		return _node != s._node;
	//	}
	//};

	//链表
	template<typename T>
	class list
	{
		typedef struct List_node<T> node;

	public:
		typedef struct List_iterator<T,T&,T*> iterator;
		typedef struct List_iterator<T,const T&,const T*> const_iterator;
		//typedef struct const_List_iterator<T> const_iterator;



		void emptyinit()
		{
			_head = new node;
			_head->_prev = _head;
			_head->_next = _head;

			_size = 0;
		}

		list()
		{
			emptyinit();
		}

		list(const list<T>& t)
		{
			emptyinit();

			for (auto& e : t)
			{
				push_back(e);
			}
		}

		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void swap(list<T>& t)
		{
			std::swap(_head, t._head);
			std::swap(_size, t._size);
		}

		list<T>& operator==(list<T> t)
		{
			swap(t);
			return *this;
		}

		void clear()
		{
			auto iter = begin();
			while (begin() != end())
			{
				iter = erase(iter);
			}
		}

		iterator begin()
		{
			/*iterator* iter = new iterator;
			iter = _head->_next;
			return iter;*/

			//return iterator(_head->_next);

			return _head->_next;
		}

		iterator end() 
		{
			return _head;
		}

		const_iterator begin() const
		{
			return _head->_next;
		}

		const_iterator end() const
		{
			return _head;
		}

		void push_back(const T& val)
		{
			/*node* newnode = new node(val);

			node* tail = _head->_prev;

			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;

			++_size;*/

			insert(end(), val);
		}

		void push_front(const T& val)
		{
			insert(begin(), val);
		}

		iterator insert(iterator p, const T& val)
		{
			node* newnode = new node(val);
			
			node* prev = p._node->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;

			newnode->_next = p._node;
			p._node->_prev = newnode;

			++_size;

			return newnode;
		}

		iterator erase(iterator p)
		{
			assert(p != end());

			node* prev = p._node->_prev;
			node* next = p._node->_next;

			prev->_next = next;
			next->_prev = prev;

			delete p._node;
			p._node = nullptr;
			--_size;

			return next;
		}

		void pop_back()
		{
			erase(--end());
		}

		void pop_front()
		{
			erase(begin());
		}

	private:
		node* _head;
		size_t _size;
	};

	template<typename Container>
	void print_container(const Container& con)
	{
		/*auto iter = con.begin();
		while (iter != con.end())
		{
			cout << *iter << " ";
			++iter;
		}*/

		for (auto e : con)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	struct AA
	{
		int _a = 1;
		int _b = 1;

		
	};

	/*ostream& operator<<(ostream& out, AA a)
	{
		out << a._a << ":" << a._b;

		return out;
	}*/

	void test_list3()
	{
		list<AA> Al;
		Al.push_back(AA());
		Al.push_back(AA());
		Al.push_back(AA());
		Al.push_back(AA());

		auto iter = Al.begin();
		while (iter != Al.end())
		{
			//cout << (*iter)._a << ":" << (*iter)._b << endl;
			cout << iter->_a << ":" << iter->_b << endl;
			cout << iter.operator->()->_a << ":" << iter.operator->()->_b << endl;
			++iter;
		}


		//for (auto e : Al)
		//{
		//	
		//	//cout << e._a << ":" << e._b << endl;
		//}


		//print_container(Al);
	}

	void test_list1()
	{
		list<int> il;
		il.push_back(1);
		il.push_back(2);
		il.push_back(3);
		il.push_back(4);

		for (auto e : il)
		{
			cout << e << " ";
		}
		//print_container(il);
	}

	void test_list2()
	{
		list<int> il;
		il.push_back(1);
		il.push_back(2);
		il.push_back(3);
		il.push_back(4);

		print_container(il);

		/*vector<int> iv(3,1);
		print_container(iv);

		cout << endl;

		string s("hello world");
		print_container(s);*/
	}


	void test_list4()
	{
		list<int> il;
		il.push_back(1);
		il.push_back(2);
		il.push_back(3);
		il.push_back(4);

		print_container(il);

		auto iter = il.begin();

		il.insert(iter, 100);
		print_container(il);

		*iter *= 1000;
		print_container(il);

		iter = il.end();
		il.insert(iter, 3333);

		print_container(il);

		il.erase(--iter);
		print_container(il);

		il.erase(il.begin());
		print_container(il);

	}

	void test_list5()
	{
		list<int> il;
		il.push_back(1);
		il.push_back(2);
		il.push_back(3);
		il.push_back(4);
		print_container(il);

		auto iter = il.begin();
		while (iter != il.end())
		{
			if (*iter % 2 == 0)
			{
				iter = il.erase(iter);
			}
			else
			{
				++iter;
			}
		}
		print_container(il);

	}

	void test_list6()
	{
		list<int> il1;
		il1.push_back(1);
		il1.push_back(2);
		il1.push_back(3);
		il1.push_back(4);
		print_container(il1);


		list<int>il2(il1);
		print_container(il2);

	}
}